package org.mozhu.learning.algo.stack.cases.calculator;

import java.util.Stack;

/**
 * 根据运算表达式计算结果，此案例重点在栈的使用，将问题简化为个位数的四则运算，如
 * 3 + 5 * 8 - 7
 * <p>
 * 算法原理：
 * 利用两个栈，其中一个用来保存操作数，另一个用来保存运算符。
 * 我们从左向右遍历表达式，
 * 1. 当遇到数字，我们就直接压入操作数栈；
 * 2. 当遇到运算符，就与运算符栈的栈顶元素进行比较，
 * 2.1 若比运算符栈顶元素优先级高，就将当前运算符压入栈，
 * 2.2 若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，
 * 然后进行计算，把计算完的结果压入操作数栈，继续比较。
 */
public class Calculator {

    Stack<Operator> operatorStacks = new SilenceStack<>();
    Stack<Integer> numberStacks = new SilenceStack<>();

    private String expression;

    public Calculator(String expression) {
        this.expression = expression;
    }

    public int calculate() {
        char[] tokens = parseToken(expression);
        return calculate(tokens);
    }

    public int calculate(char[] tokens) {
        for (char token : tokens) {
            if (Operator.isOperator(token)) {
                pushToOperatorStack(Operator.valueOf(token));
            } else if (isNumber(token)) {
                numberStacks.push(Character.getNumericValue(token));
            }
        }

        // 先弹出的作为第二个参数
        Integer second = numberStacks.pop();
        Integer first = numberStacks.pop();
        Operator lastOperator = operatorStacks.pop();
        return lastOperator.calculate(first, second);
    }

    private void pushToOperatorStack(Operator currentOperator) {
        Operator previousOperator = operatorStacks.peek();
        if (currentOperator.isPriorityHighThan(previousOperator)) {
            operatorStacks.push(currentOperator);
        } else {
            // 先弹出的作为第二个参数
            Integer second = numberStacks.pop();
            Integer first = numberStacks.pop();
            previousOperator = operatorStacks.pop();
            int result = previousOperator.calculate(first, second);
            numberStacks.push(result);
            pushToOperatorStack(currentOperator);
        }
    }

    private boolean isNumber(char token) {
        return Character.isDigit(token);
    }

    protected char[] parseToken(String expression) {
        // 问题简化为个位数的四则运算
        expression = expression.replace(" ", "");
        return expression.toCharArray();
    }

    /**
     * 元素不存在不报错
     */
    static class SilenceStack<E> extends Stack<E> {
        @Override
        public synchronized E pop() {
            return isEmpty() ? null : super.pop();
        }

        // peek只查看元素弹出栈
        @Override
        public synchronized E peek() {
            return isEmpty() ? null : super.peek();
        }
    }
}
